#define _CRT_SECURE_NO_WARNINGS

#include "TREE.h"
#include <stdlib.h>
#include <string.h>

#define DONOTCHANGE -2
#define NOTUSED -1
#define MAXNUMVALUES 100

typedef int bool;

#define TRUE  1
#define FALSE 0

static char stringValues[MAXNUMVALUES * 3]; //Temporary storage of user input of nodevalues as a string
static int nodeValues[MAXNUMVALUES]; //Temporary storage of user input of nodevalues as numbers.
static int numValues = 0; //number of values the user input, count of nodeValues.



typedef struct cellT{
	int node[2];
	struct cellT *myParent;
	struct cellT *leftChild;
	struct cellT *middleChild;
	struct cellT *rightChild;
	struct cellT *hook;
}cellT;

typedef struct treeCDT {
	cellT *tree;
} treeCDT;

cellT nodes[7];
static void printTreeC(cellT *tree);
static void populateTree();
static cellT *insertOneValue(cellT *cell, int value);
static void askUserElements(void);
cellT* newCellT(void);
static void sortNode(cellT *cell);
static void sortValuesInPlace(int *left, int *middle, int *right);
static bool isLeaf(cellT *cell);
static cellT *traverse(cellT *cell, int value);
static int isThreeNode(cellT cell);

static bool amILeftChild(cellT *meSelf);
static bool amIMiddleChild(cellT *meSelf);
static bool amIRightChild(cellT *meSelf);
static void prepareCell(cellT *cell, int node0, int node1);
static bool amITopCell(cellT *meSelf);


static cellT *cameFrom = NULL;
static cellT *currentTopCell = NULL;

void init(void){

	//stringValues = (char *)malloc(MAXNUMVALUES * 3);
	internalTree = (treeADT)malloc(sizeof(treeCDT));
	populateTree();
}



static bool amIFull(cellT *cell){

	if (cell->node[0] != NOTUSED && cell->node[1] != NOTUSED)
		return TRUE;

	return FALSE;
}

static bool amILeftChild(cellT *meSelf){

	if (meSelf->myParent != NULL)
		if (meSelf == meSelf->myParent->leftChild)
			return TRUE;

	return FALSE;
}

static bool amITopCell(cellT *meSelf){

	if (meSelf->myParent == NULL)
		return TRUE;

	return FALSE;
}

static void prepareCell(cellT *cell, int node0, int node1){

	if (node0 != DONOTCHANGE)
		cell->node[0] = node0;

	if (node1 != DONOTCHANGE)
		cell->node[1] = node1;
}

static bool amIMiddleChild(cellT *meSelf){

	if (meSelf->myParent != NULL)
		if (meSelf == meSelf->myParent->middleChild)
			return TRUE;

	return FALSE;
}

static bool amIRightChild(cellT *meSelf){

	if (meSelf->myParent != NULL)
		if (meSelf == meSelf->myParent->rightChild)
			return TRUE;

	return FALSE;
}

static void sortNode(cellT *cell){
	int temp;
	if (cell->node[0] > cell->node[1]){
		temp = cell->node[1];
		cell->node[1] = cell->node[0];
		cell->node[0] = temp;
	}
}

static void sortValuesInPlace(int *left, int *middle, int *right){

	int swap = 0;

	if (*left > *middle){
		swap = *middle;
		*middle = *left;
		*left = swap;
	}

	if (*middle > *right){
		swap = *right;
		*right = *middle;
		*middle = swap;
	}

	if (*left > *middle){
		swap = *middle;
		*middle = *left;
		*left = swap;
	}
}




cellT* newCellT(void){
	cellT *x;
	int i;
	x = (cellT*)malloc(sizeof(cellT));

	x->node[0] = NOTUSED;
	x->node[1] = NOTUSED;
	x->leftChild = NULL;
	x->middleChild = NULL;
	x->rightChild = NULL;
	x->myParent = NULL;
	x->hook = NULL;
	return (x);
}

static void askUserElements(void){
	char *token;
	char *nextToken = NULL;
	int i;
	int node = 0;
	stringValues[0] = '\0';

	numValues = 0;

	printf("\nMaximum %d elements can be inserted at once.\n"
		"Enter an element or elements delimited by spaces: \n", MAXNUMVALUES);

	scanf("%[0-9 -]s", stringValues); // MAXNUMVALUES, stdin);

	fflush(stdin);

	token = strtok_s(stringValues, " ", &nextToken);


	for (i = 0; token != NULL && i < MAXNUMVALUES; i++){
		node = atoi(token);
		nodeValues[numValues++] = node;

		//printf("%d\n", nodeValues[i]);

		token = strtok_s(NULL, " ", &nextToken);
	}

	//Sleep(2000);
}

treeADT newTree(){
	treeADT tree;
	tree = (treeADT)malloc(sizeof(treeCDT));
	tree->tree = newCellT();

	currentTopCell = tree->tree;

	cameFrom = tree->tree;
	return (tree);
}


void deleteElement(treeADT tree){


}

void deleteTree(treeADT tree){


}

void printTree(treeADT tree){

	printTreeC(currentTopCell);

}

static void printTreeC(cellT *tree){

	if (tree->leftChild == NULL
		&& tree->middleChild == NULL
		&& tree->rightChild == NULL){
		printf("(%d,%d)", tree->node[0], tree->node[1]);
		return;
	}

	//printf("(Node23 (%d,%d) (%d,%d) (%d,%d) (%d,%d))");
	printf("(Node23 (%d,%d) ", tree->node[0], tree->node[1]);

	if (tree->leftChild != NULL)
		printTreeC(tree->leftChild);
	else
		printf("(NIL)");

	printf(" ");

	if (tree->middleChild != NULL)
		printTreeC(tree->middleChild);
	else
		printf("(NIL)");

	printf(" ");

	if (tree->rightChild != NULL)
		printTreeC(tree->rightChild);
	else
		printf("(NIL)");

	printf(")");

}

static void populateTree(){
	/*
	internalTree->tree = &nodes[0];

	internalTree->tree->node[0] = 32;
	internalTree->tree->node[1] = 86;

	internalTree->tree->leftChild = &nodes[1];
	internalTree->tree->middleChild = &nodes[2];
	internalTree->tree->rightChild = &nodes[3];

	internalTree->tree->leftChild->node[0] = 15;
	internalTree->tree->leftChild->node[1] = 25;
	internalTree->tree->middleChild->node[0] = 45;
	internalTree->tree->middleChild->node[1] = 55;
	internalTree->tree->rightChild->node[0] = 95;
	internalTree->tree->rightChild->node[1] = 104;

	internalTree->tree->rightChild->leftChild = NULL;
	internalTree->tree->rightChild->middleChild = NULL;
	internalTree->tree->rightChild->rightChild = NULL;

	internalTree->tree->middleChild->rightChild = NULL;
	internalTree->tree->middleChild->middleChild = NULL;
	internalTree->tree->middleChild->leftChild = NULL;

	internalTree->tree->leftChild->rightChild = &nodes[4];
	internalTree->tree->leftChild->middleChild = &nodes[5];
	internalTree->tree->leftChild->leftChild = &nodes[6];

	internalTree->tree->leftChild->rightChild->node[0] = 10;
	internalTree->tree->leftChild->rightChild->node[1] = 14;

	internalTree->tree->leftChild->middleChild->node[0] = 16;
	internalTree->tree->leftChild->middleChild->node[1] = 17;

	internalTree->tree->leftChild->leftChild->node[0] = 28;
	internalTree->tree->leftChild->leftChild->node[1] = 32;

	internalTree->tree->leftChild->rightChild->leftChild = NULL;
	internalTree->tree->leftChild->rightChild->middleChild = NULL;
	internalTree->tree->leftChild->rightChild->rightChild = NULL;

	internalTree->tree->leftChild->middleChild->leftChild = NULL;
	internalTree->tree->leftChild->middleChild->middleChild = NULL;
	internalTree->tree->leftChild->middleChild->rightChild = NULL;

	internalTree->tree->leftChild->leftChild->leftChild = NULL;
	internalTree->tree->leftChild->leftChild->middleChild = NULL;
	internalTree->tree->leftChild->leftChild->rightChild = NULL;
	*/
}

static bool isLeaf(cellT *cell){

	if (cell->leftChild == NULL)
		return TRUE;

	return FALSE;
}

static cellT *traverse(cellT *cell, int value){
	if (cell == NULL || isLeaf(cell)){
		return cell;
	}

	else if (isThreeNode(*cell)){

		if (value < cell->node[0])
			traverse(cell->leftChild, value);
		else if (value > cell->node[0] && value < cell->node[1])
			traverse(cell->middleChild, value);
		else
			traverse(cell->rightChild, value);
	}
	else{
		if (value < cell->node[0])
			traverse(cell->leftChild, value);
		else
			traverse(cell->rightChild, value);
	}
}

static int isThreeNode(cellT cell){
	int i;

	for (i = 0; i < 2; i++){
		if (cell.node[i] == NOTUSED)
			return FALSE;
	}

	return TRUE;
}

static cellT *insertOneValue(cellT *cell, int value){

	if (cell == NULL)
		cell = newCellT();

	if (value == cell->node[0] || value == cell->node[1])
		return cell;
	//////////////////////////////////////////////


	//top-case
	if (amIFull(cell) && amITopCell(cell)){

		cellT *newTopCell = newCellT();
		cellT *newLeftCell = newCellT();
		cellT *newRightCell = newCellT();

		sortValuesInPlace(&cell->node[0], &value, &cell->node[1]);

		*newTopCell = *cell;
		*newLeftCell = *cell;
		*newRightCell = *cell;

		prepareCell(newTopCell, value, NOTUSED);
		prepareCell(newLeftCell, cell->node[0], NOTUSED);
		prepareCell(newRightCell, cell->node[1], NOTUSED);

		newTopCell->leftChild = newLeftCell;
		newTopCell->middleChild = NULL;
		newTopCell->rightChild = newRightCell;

		newLeftCell->myParent = newTopCell;
		newRightCell->myParent = newTopCell;

		newLeftCell->rightChild; //untouched

		if (amIMiddleChild(cameFrom)){
			newLeftCell->leftChild;//untouched
			newLeftCell->rightChild = cell->middleChild;
			newRightCell->leftChild = cell->hook;
			newRightCell->rightChild; //untouched
		}

		if (amILeftChild(cameFrom)){
			newLeftCell->leftChild; //untouched
			newLeftCell->rightChild = cell->hook;
			newRightCell->leftChild = cell->middleChild;
		}

		
		newLeftCell->middleChild = NULL;
		newRightCell->middleChild = NULL;
		newTopCell->hook = NULL;
		newLeftCell->hook = NULL;
		newRightCell->hook = NULL;

		currentTopCell = newTopCell;
		return cell;
	} 

	//2-node right child full, parent have space
	if (amIFull(cell) && !amIFull(cell->myParent) && amIRightChild(cell)){

		cellT *newMiddleCell = newCellT();

		sortValuesInPlace(&cell->node[0], &value, &cell->node[1]);

		*newMiddleCell = *cell;

		prepareCell(newMiddleCell, DONOTCHANGE, NOTUSED);

		cell->myParent->middleChild = newMiddleCell;

		newMiddleCell->hook = NULL;
		newMiddleCell->leftChild = NULL;
		newMiddleCell->middleChild = NULL;
		newMiddleCell->rightChild = NULL;

		prepareCell(cell, cell->node[1], NOTUSED);

		insertOneValue(cell->myParent, value);
		return cell;
	}

	//2-node left child full, parent have space
	if (amIFull(cell) && !amIFull(cell->myParent) && amILeftChild(cell)){

		cellT *newMiddleCell = newCellT();

		sortValuesInPlace(&cell->node[0], &value, &cell->node[1]);

		*newMiddleCell = *cell;

		prepareCell(newMiddleCell, cell->node[1], NOTUSED);

		cell->myParent->middleChild = newMiddleCell;

		newMiddleCell->hook = NULL;
		newMiddleCell->leftChild = NULL;
		newMiddleCell->middleChild = NULL;
		newMiddleCell->rightChild = NULL;

		prepareCell(cell, DONOTCHANGE, NOTUSED);

		insertOneValue(cell->myParent, value);
		return cell;
	}


	//left-case
	if (amIFull(cell) && amILeftChild(cell)){

		cellT *hookCell = newCellT();

		sortValuesInPlace(&cell->node[0], &value, &cell->node[1]);

		*hookCell = *cell;

		prepareCell(hookCell, cell->node[1], NOTUSED);

		cell->myParent->hook = hookCell;

		cell->rightChild = hookCell->hook;

		hookCell->leftChild = cell->middleChild;
		hookCell->middleChild = NULL;
		hookCell->rightChild = cell->rightChild;

		prepareCell(cell, DONOTCHANGE, NOTUSED);

		cameFrom = cell;

		insertOneValue(cell->myParent, value);
		return cell;
	}

	//middle-case
	if (amIFull(cell) && amIMiddleChild(cell)){


		cellT *hookCell = newCellT();

		sortValuesInPlace(&cell->node[0], &value, &cell->node[1]);

		*hookCell = *cell;

		prepareCell(hookCell, cell->node[1], NOTUSED);

		cell->myParent->hook = hookCell;

		hookCell->leftChild = cell->hook;
		hookCell->rightChild = cell->rightChild;
		hookCell->middleChild = NULL;
		hookCell->hook = NULL;

		prepareCell(cell, DONOTCHANGE, NOTUSED);

		cameFrom = cell;
		insertOneValue(cell->myParent, value);
		return cell;
	}

	//right-case
	if (amIFull(cell) && amIRightChild(cell)){


		cellT *hookCell = newCellT();
		 
		sortValuesInPlace(&cell->node[0], &value, &cell->node[1]);

		*hookCell = *cell;

		

		prepareCell(hookCell, cell->node[1], NOTUSED);

		cell->myParent->hook = hookCell;

		hookCell->rightChild = cell->hook;
		hookCell->leftChild = cell->rightChild;
		hookCell->middleChild = NULL;

		prepareCell(cell, DONOTCHANGE, NOTUSED);
		hookCell->hook = NULL;

		cameFrom = cell;
		insertOneValue(cell->myParent, value);
		return cell;
	}



	////////////////////////////////////////
	if (cell->node[0] == NOTUSED){
		cell->node[0] = value;
		return cell;
	}

	if (cell->node[1] == NOTUSED){
		cell->node[1] = value;
		sortNode(cell);
		return cell;
	}

	return cell;
}

void  insertElements(treeADT *tree){

	int i;

	askUserElements();


	for (i = 0; i < numValues; i++){
		//traverse((*tree)->tree, nodeValues[i]);
		internalTree->tree = traverse(currentTopCell, nodeValues[i]);
		//(*tree)->tree = insertOneValue((*tree)->tree, nodeValues[i]);
		internalTree->tree = insertOneValue(internalTree->tree, nodeValues[i]);
	}

}